/* Í·ÎÄ¼þÀï¸÷¸öº¯ÊýµÄ¾ßÌåÊµÏÖ
*/

#include "Maze.h"
#include <iostream>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <string>

using namespace std;

namespace liandan{

void blockFromAToB(TrackNode A, TrackNode B, int indexOfA, vector<Cell>forkCells);

double min(double a, double b){
	return (a<b)? a:b;
}

struct assistNode
{
	double up_time;
	double bottom_time;
	double left_time;
	double right_time;

	// 0: from up 1: from bottom 2: from left 3: from right
	int up_direction;
	int bottom_direction;
	int left_direction;
	int right_direction;

	assistNode(){
		up_time = infinateDouble;
		up_direction = -1;
		bottom_time = infinateDouble;
		bottom_direction = -1;
		left_time = infinateDouble;
		left_direction = -1;
		right_time = infinateDouble;
		right_direction = -1;
	}
};

Maze::Maze(int height, int width, int startRow, int startColumn, int endRow, int endColumn){
	this->height = height;
	this->width = width;
	this->startRow = startRow;
	this->startColumn = startColumn;
	this->endRow = endRow;
	this->endColumn = endColumn;

	Cell unknown_cell;
	for (int i = 0; i < height; i++){
		vector<Cell> newRow;
		for (int j = 0; j < width; j++){
			newRow.push_back(unknown_cell);
		}
		this->mazeData.push_back(newRow);
	}
}

Maze::Maze(int height, int width, int startRow, int startColumn, int endRow, int endColumn, vector<Cell> mazeData){
	this->height = height;
	this->width = width;
	this->startRow = startRow;
	this->startColumn = startColumn;
	this->endRow = endRow;
	this->endColumn = endColumn;

	for (int i = 0; i < height; i++){
		vector<Cell> newRow;
		for (int j = 0; j < width; j++){
			newRow.push_back(mazeData[i * width + j]);
		}
		this->mazeData.push_back(newRow);
	}
}

void Maze::setEndpoint(int sR, int sC, int eR, int eC){
	startRow=sR;
	startColumn=sC;
	endRow=eR;
	endColumn=eC;
}

void Maze::calculateHeight(double cornerRate){
	queue<int> queue_row;
	queue<int> queue_column;
	vector< vector<assistNode> > assistMazeTime;

	for (int i = 0; i < height; i++){
		vector<assistNode> newRow;
		for (int j = 0; j < width; j++){
			newRow.push_back(assistNode());
		}
		assistMazeTime.push_back(newRow);
	}

	assistMazeTime[startRow][startColumn].up_time = 0;
	assistMazeTime[startRow][startColumn].bottom_time = 0;
	assistMazeTime[startRow][startColumn].right_time = 0;
	assistMazeTime[startRow][startColumn].left_time = 0;
	queue_row.push(startRow);
	queue_column.push(startColumn);

	double line_road_time = 1;
	double corner_road_time = line_road_time * cornerRate;

	while (!queue_row.empty()){

		// dequeue
		int this_row = queue_row.front();
		int this_column = queue_column.front();
		assistNode this_node = assistMazeTime[this_row][this_column];
		queue_row.pop();
		queue_column.pop();

		if (this_row > 0 && mazeData[this_row][this_column].up != 0){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.left_time + corner_road_time < temp_time){
				temp_time = this_node.left_time + corner_road_time;
				temp_direction = 2;
			}
			if (this_node.right_time + corner_road_time < temp_time){
				temp_time = this_node.right_time + corner_road_time;
				temp_direction = 3;
			}
			if (this_node.bottom_time + line_road_time < temp_time){
				temp_time = this_node.bottom_time + line_road_time;
				temp_direction = 1;
			}
			if (temp_time < assistMazeTime[this_row - 1][this_column].bottom_time){
				assistMazeTime[this_row - 1][this_column].bottom_time = temp_time;
				assistMazeTime[this_row - 1][this_column].bottom_direction = temp_direction;

				// enqueue
				queue_row.push(this_row - 1);
				queue_column.push(this_column);
			}
		}

		if (this_column > 0 && mazeData[this_row][this_column].left != 0){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.up_time + corner_road_time < temp_time){
				temp_time = this_node.up_time + corner_road_time;
				temp_direction = 0;
			}
			if (this_node.bottom_time + corner_road_time < temp_time){
				temp_time = this_node.bottom_time + corner_road_time;
				temp_direction = 1;
			}
			if (this_node.right_time + line_road_time < temp_time){
				temp_time = this_node.right_time + line_road_time;
				temp_direction = 3;
			}
			if (temp_time < assistMazeTime[this_row][this_column - 1].right_time){
				assistMazeTime[this_row][this_column - 1].right_time = temp_time;
				assistMazeTime[this_row][this_column - 1].right_direction = temp_direction;

				// enqueue
				queue_row.push(this_row);
				queue_column.push(this_column - 1);
			}
		}

		if (this_row < height - 1 && mazeData[this_row][this_column].bottom != 0){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.left_time + corner_road_time < temp_time){
				temp_time = this_node.left_time + corner_road_time;
				temp_direction = 2;
			}
			if (this_node.right_time + corner_road_time < temp_time){
				temp_time = this_node.right_time + corner_road_time;
				temp_direction = 3;
			}
			if (this_node.up_time + line_road_time < temp_time){
				temp_time = this_node.up_time + line_road_time;
				temp_direction = 0;
			}
			if (temp_time < assistMazeTime[this_row + 1][this_column].up_time){
				assistMazeTime[this_row + 1][this_column].up_time = temp_time;
				assistMazeTime[this_row + 1][this_column].up_direction = temp_direction;

				// enqueue
				queue_row.push(this_row + 1);
				queue_column.push(this_column);
			}
		}

		if (this_column < width - 1 && mazeData[this_row][this_column].right != 0){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.up_time + corner_road_time < temp_time){
				temp_time = this_node.up_time + corner_road_time;
				temp_direction = 0;
			}
			if (this_node.bottom_time + corner_road_time < temp_time){
				temp_time = this_node.bottom_time + corner_road_time;
				temp_direction = 1;
			}
			if (this_node.left_time + line_road_time < temp_time){
				temp_time = this_node.left_time + line_road_time;
				temp_direction = 2;
			}
			if (temp_time < assistMazeTime[this_row][this_column + 1].left_time){
				assistMazeTime[this_row][this_column + 1].left_time = temp_time;
				assistMazeTime[this_row][this_column + 1].left_direction = temp_direction;

				// enqueue
				queue_row.push(this_row);
				queue_column.push(this_column + 1);
			}
		}
	}	//	end of while

	for (int i = 0; i < height; i++){
		for (int j = 0; j < width; j++){
			double temp = infinateDouble;
			temp = (temp < assistMazeTime[i][j].up_time)? temp:assistMazeTime[i][j].up_time;
			temp = (temp < assistMazeTime[i][j].bottom_time)? temp:assistMazeTime[i][j].bottom_time;
			temp = (temp < assistMazeTime[i][j].left_time)? temp:assistMazeTime[i][j].left_time;
			temp = (temp < assistMazeTime[i][j].right_time)? temp:assistMazeTime[i][j].right_time;
			mazeData[i][j].height = temp;
			cout<<mazeData[i][j].height<<"\t"; //***测试用
		}
		cout<<endl; //***测试用
	}	// end of height calculate
	cout<<"==================="<<endl;//***测试用
}

void Maze::legitimation(){
	for (int i = 0; i < height; i++){
		for (int j = 0; j < width; j++){
			if (i > 0 && mazeData[i-1][j].bottom >= 0)
				mazeData[i][j].up = mazeData[i-1][j].bottom;
			if (j > 0 && mazeData[i][j-1].right >= 0)
				mazeData[i][j].left = mazeData[i][j-1].right;
			if (i < height - 1 && mazeData[i+1][j].up >= 0)
				mazeData[i][j].bottom = mazeData[i+1][j].up;
			if (j < width - 1 && mazeData[i][j+1].left >= 0)
				mazeData[i][j].right = mazeData[i][j+1].left;
		}
	}
}

bool Maze::isLegal(){
	for (int i = 0; i < height; i++){
		for (int j = 0; j < width; j++){
			if (i<height-1&&mazeData[i+1][j].up != mazeData[i][j].bottom){
				cout<<"Cell "<<i<<"-"<<j<<" has discrepancy with cell "<<i+1<<"-"<<j<<endl;
				return false;
			}
			if (j<width-1&&mazeData[i][j+1].left != mazeData[i][j].right){
				cout<<"Cell "<<i<<"-"<<j<<" has discrepancy with cell "<<i<<"-"<<j+1<<endl;
				return false;
			}
			if (i==0&&mazeData[i][j].up!=0){
				cout<<"Cell "<<i<<"-"<<j<<"got a boundary error"<<endl;
				return false;
			}
			if (j==0&&mazeData[i][j].left!=0){
				cout<<"Cell "<<i<<"-"<<j<<"got a boundary error"<<endl;
				return false;
			}
			if (i==height-1&&mazeData[i][j].bottom!=0){
				cout<<"Cell "<<i<<"-"<<j<<"got a boundary error"<<endl;
				return false;
			}
			if (j==width-1&&mazeData[i][j].right!=0){
				cout<<"Cell "<<i<<"-"<<j<<"got a boundary error"<<endl;
				return false;
			}
		}
	}
	return true;
}

Track Maze::getBestTrack(double cornerRate){
	queue<int> queue_row;
	queue<int> queue_column;
	vector< vector<assistNode> > assistMazeTime;

	for (int i = 0; i < height; i++){
		vector<assistNode> newRow;
		for (int j = 0; j < width; j++){
			newRow.push_back(assistNode());
		}
		assistMazeTime.push_back(newRow);
	}

	assistMazeTime[startRow][startColumn].up_time = 0;
	assistMazeTime[startRow][startColumn].bottom_time = 0;
	assistMazeTime[startRow][startColumn].right_time = 0;
	assistMazeTime[startRow][startColumn].left_time = 0;
	queue_row.push(startRow);
	queue_column.push(startColumn);

	double line_road_time = 1;
	double corner_road_time = line_road_time * cornerRate;

	while (!queue_row.empty()){

		// dequeue
		int this_row = queue_row.front();
		int this_column = queue_column.front();
		assistNode this_node = assistMazeTime[this_row][this_column];
		queue_row.pop();
		queue_column.pop();

		if (this_row > 0 && mazeData[this_row][this_column].up == 1){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.left_time + corner_road_time < temp_time){
				temp_time = this_node.left_time + corner_road_time;
				temp_direction = 2;
			}
			if (this_node.right_time + corner_road_time < temp_time){
				temp_time = this_node.right_time + corner_road_time;
				temp_direction = 3;
			}
			if (this_node.bottom_time + line_road_time < temp_time){
				temp_time = this_node.bottom_time + line_road_time;
				temp_direction = 1;
			}
			if (temp_time < assistMazeTime[this_row - 1][this_column].bottom_time){
				assistMazeTime[this_row - 1][this_column].bottom_time = temp_time;
				assistMazeTime[this_row - 1][this_column].bottom_direction = temp_direction;

				// enqueue
				queue_row.push(this_row - 1);
				queue_column.push(this_column);
			}
		}

		if (this_column > 0 && mazeData[this_row][this_column].left == 1){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.up_time + corner_road_time < temp_time){
				temp_time = this_node.up_time + corner_road_time;
				temp_direction = 0;
			}
			if (this_node.bottom_time + corner_road_time < temp_time){
				temp_time = this_node.bottom_time + corner_road_time;
				temp_direction = 1;
			}
			if (this_node.right_time + line_road_time < temp_time){
				temp_time = this_node.right_time + line_road_time;
				temp_direction = 3;
			}
			if (temp_time < assistMazeTime[this_row][this_column - 1].right_time){
				assistMazeTime[this_row][this_column - 1].right_time = temp_time;
				assistMazeTime[this_row][this_column - 1].right_direction = temp_direction;

				// enqueue
				queue_row.push(this_row);
				queue_column.push(this_column - 1);
			}
		}

		if (this_row < height - 1 && mazeData[this_row][this_column].bottom == 1){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.left_time + corner_road_time < temp_time){
				temp_time = this_node.left_time + corner_road_time;
				temp_direction = 2;
			}
			if (this_node.right_time + corner_road_time < temp_time){
				temp_time = this_node.right_time + corner_road_time;
				temp_direction = 3;
			}
			if (this_node.up_time + line_road_time < temp_time){
				temp_time = this_node.up_time + line_road_time;
				temp_direction = 0;
			}
			if (temp_time < assistMazeTime[this_row + 1][this_column].up_time){
				assistMazeTime[this_row + 1][this_column].up_time = temp_time;
				assistMazeTime[this_row + 1][this_column].up_direction = temp_direction;

				// enqueue
				queue_row.push(this_row + 1);
				queue_column.push(this_column);
			}
		}

		if (this_column < width - 1 && mazeData[this_row][this_column].right == 1){
			double temp_time = infinateDouble;
			int temp_direction = -1;
			if (this_node.up_time + corner_road_time < temp_time){
				temp_time = this_node.up_time + corner_road_time;
				temp_direction = 0;
			}
			if (this_node.bottom_time + corner_road_time < temp_time){
				temp_time = this_node.bottom_time + corner_road_time;
				temp_direction = 1;
			}
			if (this_node.left_time + line_road_time < temp_time){
				temp_time = this_node.left_time + line_road_time;
				temp_direction = 2;
			}
			if (temp_time < assistMazeTime[this_row][this_column + 1].left_time){
				assistMazeTime[this_row][this_column + 1].left_time = temp_time;
				assistMazeTime[this_row][this_column + 1].left_direction = temp_direction;

				// enqueue
				queue_row.push(this_row);
				queue_column.push(this_column + 1);
			}
		}
	}	//	end of while

	for (int i = 0; i < height; i++){
		for (int j = 0; j < width; j++){
			double temp = infinateDouble;
			temp = (temp < assistMazeTime[i][j].up_time)? temp:assistMazeTime[i][j].up_time;
			temp = (temp < assistMazeTime[i][j].bottom_time)? temp:assistMazeTime[i][j].bottom_time;
			temp = (temp < assistMazeTime[i][j].left_time)? temp:assistMazeTime[i][j].left_time;
			temp = (temp < assistMazeTime[i][j].right_time)? temp:assistMazeTime[i][j].right_time;
			if (temp < mazeData[i][j].height)
				mazeData[i][j].height = temp;
			//cout<<mazeData[i][j].height<<"\t"; //***测试用
		}
		//cout<<endl; //***测试用
	}	// end of height calculate

	//cout<< "=========================================" << endl;	//***测试用

	Track result(height, width);
	result.endRow = endRow;
	result.endColumn = endColumn;
	if (mazeData[endRow][endColumn].height >= infinateDouble){

		// best track not exists
		result.startRow = -1;
		result.endColumn = -1;
		return result;

	}

	int now_row = endRow;
	int now_column =endColumn;
	TrackNode now_node;
	double now_time= infinateDouble;
	int now_direction = -1;
	int next_direction = -1;
	//cout<<now_row<<"\t"<<now_column<<endl;	//***测试用

	if (assistMazeTime[endRow][endColumn].up_time < now_time){
		now_time = assistMazeTime[endRow][endColumn].up_time;
		now_direction = 0;
		next_direction = assistMazeTime[endRow][endColumn].up_direction;
	}
	if (assistMazeTime[endRow][endColumn].bottom_time < now_time){
		now_time = assistMazeTime[endRow][endColumn].bottom_time;
		now_direction = 1;
		next_direction = assistMazeTime[endRow][endColumn].bottom_direction;
	}
	if (assistMazeTime[endRow][endColumn].left_time < now_time){
		now_time = assistMazeTime[endRow][endColumn].left_time;
		now_direction = 2;
		next_direction = assistMazeTime[endRow][endColumn].left_direction;
	}
	if (assistMazeTime[endRow][endColumn].right_time < now_time){
		now_time = assistMazeTime[endRow][endColumn].right_time;
		now_direction = 3;
		next_direction = assistMazeTime[endRow][endColumn].right_direction;
	}

	now_node.cellRow = endRow;
	now_node.cellColumn = endColumn;
	now_node.time = now_time;
	result.trackData.push_back(now_node);

	while(next_direction != -1){
		switch (now_direction){
		case 0:
			now_row--;
			break;
		case 1:
			now_row++;
			break;
		case 2:
			now_column--;
			break;
		case 3:
			now_column++;
			break;
		}
		now_direction = next_direction;

		switch (next_direction){
		case 0:
			now_time = assistMazeTime[now_row][now_column].up_time;
			next_direction = assistMazeTime[now_row][now_column].up_direction;
			break;
		case 1:
			now_time = assistMazeTime[now_row][now_column].bottom_time;
			next_direction = assistMazeTime[now_row][now_column].bottom_direction;
			break;
		case 2:
			now_time = assistMazeTime[now_row][now_column].left_time;
			next_direction = assistMazeTime[now_row][now_column].left_direction;
			break;
		case 3:
			now_time = assistMazeTime[now_row][now_column].right_time;
			next_direction = assistMazeTime[now_row][now_column].right_direction;
			break;
		}

		now_node.cellRow = now_row;
		now_node.cellColumn = now_column;
		now_node.time = now_time;
		result.trackData.push_back(now_node);
		//cout<<now_row<<"\t"<<now_column<<endl;	//***测试用
	}

	// 换顺序啊，起点在前面
	for (int i = 0; i < result.trackData.size() / 2; i++){
		TrackNode temp = result.trackData[i];
		result.trackData[i] = result.trackData[result.trackData.size() - i - 1];
		result.trackData[result.trackData.size() - i - 1] = temp;
	}
	result.startRow = startRow;
	result.startColumn = startColumn;

	
	/*
	for (int i = 0; i < result.trackData.size(); i++)
	cout<<result.trackData[i].cellRow<<"\t"<<result.trackData[i].cellColumn<<"\t"<<result.trackData[i].time<<endl;
	cout<<"===================================="<<endl;
	char x;
	cin>>x;
	//***测试用
	*/
	

	return result;
}

Track Maze::getBestTrackBasedOnExploration(double cornerRate, Track exploration){
	return exploration.drawMaze(*this).getBestTrack(cornerRate);
}

Maze::~Maze(){
	mazeData.clear();
}

void Track::setEndpoint(int sR, int sC, int eR, int eC){
	startRow=sR;
	startColumn=sC;
	endRow=eR;
	endColumn=eC;
}

double Track::getCoverage(){
	vector<vector<int>> table;
	vector<int> row;
	int counter=0;

	for (int i=0; i<height; i++){
		for (int i1=0; i1<width; i1++){
			row.push_back(0);
		}
		table.push_back(row);
		row.clear();
	}
	for (int i=0; i<this->trackData.size(); i++){
		table[this->trackData[i].cellRow][this->trackData[i].cellColumn]++;
	}
	for (int i=0; i<height; i++){
		for (int i1=0; i1<width; i1++){
			if (table[i][i1]>0){
				counter++;
			}
		}
	}
	return double(counter)/(width*height);
}

double Track::getRepetationRate(){
	vector<vector<int>> table;
	vector<int> row;
	int counter=0;

	for (int i=0; i<height; i++){
		for (int i1=0; i1<width; i1++){
			row.push_back(0);
		}
		table.push_back(row);
		row.clear();
	}
	for (unsigned int i=0; i<this->trackData.size(); i++){
		table[this->trackData[i].cellRow][this->trackData[i].cellColumn]++;
	}
	for (int i=0; i<height; i++){
		for (int i1=0; i1<width; i1++){
			if (table[i][i1]>1){
				counter++;
			}
		}
	}
	return double(counter)/(this->trackData.size());
}

int Track::getCircleLength(){
	vector<vector<int>> table;
	vector<int> row;
	int counter=0;

	for (int i=0; i<width; i++){
		//Fill the table with 0;
		row.push_back(0);
	}
	for (int i=0; i<height; i++){
		table.push_back(row);
	}
	for (int i=0; i<this->trackData.size(); i++){
		table[this->trackData[i].cellRow][this->trackData[i].cellColumn]++;
		//Once passed, the cell increased by 1;
		if (table[this->trackData[i].cellRow][this->trackData[i].cellColumn]>1){
			//Meet the cell which already meeted;
			for(int i1=0; i1<this->trackData.size(); i1++){
				if ((this->trackData[i1].cellRow==this->trackData[i].cellRow)&&(this->trackData[i1].cellColumn==this->trackData[i].cellColumn)){
					//Find the meeting point;
					for(int i2=0; i2<i-i1; i2++){
						//Expurgate the redundancy;
						this->trackData.pop_back();
						counter++;
						table[this->trackData[i-i2].cellRow][this->trackData[i-i2].cellColumn]--;
					}
				}
			}
		}
	}
	return counter;
}

double Track::getIdleTime(double idealTime, double cornerRate, double UTurnRate){
	double idleTime=0;
	for (int i=1; i<this->trackData.size()-1; i++){
		switch(this->trackData[i].getTurnState(this->trackData[i-1], this->trackData[i+1])){
		case 1:
			if (this->trackData[i+1].time-this->trackData[i].time-idealTime>0){
				idleTime+=this->trackData[i+1].time-this->trackData[i].time-idealTime;
			}
			break;
		case 2:
		case 3:
			if (this->trackData[i+1].time-this->trackData[i].time-idealTime*cornerRate>0){
				idleTime+=this->trackData[i+1].time-this->trackData[i].time-idealTime*cornerRate;
			}
			break;
		case 4:
			if (this->trackData[i+1].time-this->trackData[i].time-idealTime*UTurnRate>0){
				idleTime+=this->trackData[i+1].time-this->trackData[i].time-idealTime*UTurnRate;
			}
			break;
		default:
			break;
		}
	}
	return idleTime;
}

double Track::getVarietyOfAlternation(Maze theMaze){
	vector<TrackNode> forkNodes;
	vector<Cell> forkCells;
	double totalJob=0;
	double goodJob=0;

	for (int num=0; num<this->trackData.size()-1; num++){
		//Judge if this is a fork node;
		if (theMaze.mazeData[this->trackData[num].cellRow][this->trackData[num].cellColumn].getState()>2){
			int forkIndex=-1;

			//Judge if the node has been passed;
			for (int num1=0; num1<forkNodes.size(); num1++){
				if (forkNodes[num1].cellColumn==this->trackData[num].cellColumn&&forkNodes[num1].cellRow==this->trackData[num].cellRow){
					forkIndex=num1;
					break;
				}
			}
			
			//If the node has not been passed.
			if (forkIndex==-1){
				forkNodes.push_back(this->trackData[num]);
				forkCells.push_back(theMaze.mazeData[this->trackData[num].cellRow][this->trackData[num].cellColumn]);
				forkIndex=forkCells.size()-1;
			}
			if (num!=0){
				blockFromAToB(this->trackData[num], this->trackData[num-1], forkIndex, forkCells);
			}
			
			//If there are exits left;
			if (forkCells[forkIndex].getState()<4){
				totalJob++;
				int orientation;
				orientation=this->trackData[num].getRelitivePosition(this->trackData[num+1]);
				switch (orientation){
				case 1:
					if (forkCells[forkIndex].left==1){
						goodJob++;
						forkCells[forkIndex].left=1;
					}
					break;
				case 2:
					if (forkCells[forkIndex].up==1){
						goodJob++;
						forkCells[forkIndex].up=1;
					}
					break;
				case 3:
					if (forkCells[forkIndex].right==1){
						goodJob++;
						forkCells[forkIndex].right=1;
					}
					break;
				case 4:
					if (forkCells[forkIndex].bottom==1){
						goodJob++;
						forkCells[forkIndex].bottom=1;
					}
					break;
				default:
					break;
				}
			}
		}
	}
	return goodJob/totalJob;
}

Maze Track::drawMaze(Maze maze)
{
	if (!maze.isLegal()){
		cout<<"Error: The maze is not legal!"<<endl;
		return Maze(0,0,0,0,0,0);
	}

	if (/*startRow != maze.startRow || startColumn != maze.startColumn 
		|| endRow != maze.endRow || endColumn != maze.endColumn
		||*/ width != maze.width || height != maze.height){
			cout<<"Error: The track is not consistent with the maze!"<<endl;
			return Maze(0,0,0,0,0,0);
	}

	bool check_not_contineous = false;
	for (int i = 1; i < trackData.size(); i++){
		if (trackData[i].cellRow == trackData[i-1].cellRow){
			if (abs(trackData[i].cellColumn - trackData[i-1].cellColumn)>1){
				check_not_contineous = true;
				break;
			}
		} else if (trackData[i].cellColumn == trackData[i-1].cellColumn){
			if (abs(trackData[i].cellRow - trackData[i-1].cellRow)>1){
				check_not_contineous = true;
				break;
			}
		} else {
			check_not_contineous = true;
			break;
		}
	}
	if (check_not_contineous){
		cout<<"Error: The track is not legal."<<endl;
		return Maze(0,0,0,0,0,0);
	}

	Maze result(height, width, startRow, startColumn, endRow, endColumn);
	for (int i = 0; i < trackData.size(); i++){
		int now_row = trackData[i].cellRow;
		int now_column = trackData[i].cellColumn;

		result.mazeData[now_row][now_column] = maze.mazeData[now_row][now_column];

		if (now_row > 0){
			result.mazeData[now_row - 1][now_column].bottom = result.mazeData[now_row][now_column].up;
		}
		if (now_column > 0){
			result.mazeData[now_row][now_column - 1].right = result.mazeData[now_row][now_column].left;
		}
		if (now_row < height - 1){
			result.mazeData[now_row + 1][now_column].up = result.mazeData[now_row][now_column].bottom;
		}
		if (now_column < width - 1){
			result.mazeData[now_row][now_column + 1].left = result.mazeData[now_row][now_column].right;
		}
	}

	return result;
}

int Cell::getState()
{
	int openDirection=0;
	if (this->bottom==1){
		openDirection++;
	}
	if (this->up==1){
		openDirection++;
	}
	if (this->left==1){
		openDirection++;
	}
	if (this->right==1){
		openDirection++;
	}
	return openDirection;
}

int TrackNode::getRelitivePosition(TrackNode anotherNode)
{
	if ((*this).getDistance(anotherNode)>1){
		return 0;
	}
	else {
		if (this->cellColumn>anotherNode.cellColumn){
			return 1;
		}
		else if (this->cellColumn<anotherNode.cellColumn){
			return 3;
		}
		else if (this->cellRow>anotherNode.cellRow){
			return 2;
		}
		else{
			return 4;
		}
	}
}

void blockFromAToB(TrackNode A, TrackNode B, int indexOfA, vector<Cell>forkCells)
{
	switch (A.getRelitivePosition(B)){
	case 0:
		break;
	case 1:
		forkCells[indexOfA].left=1;
		break;
	case 2:
		forkCells[indexOfA].up=1;
		break;
	case 3:
		forkCells[indexOfA].right=1;
		break;
	case 4:
		forkCells[indexOfA].bottom=1;
		break;
	default:
		break;
	}
}

int TrackNode::getTurnState(TrackNode previous, TrackNode next){
	if ((*this).getDistance(previous)>1||(*this).getDistance(next)>1){
		return 0;
	}
	else if (previous.getRelitivePosition(*this)-(*this).getRelitivePosition(next)==1||previous.getRelitivePosition(*this)-(*this).getRelitivePosition(next)==-3){
		return 1;
	}
	else if (previous.getRelitivePosition(*this)-(*this).getRelitivePosition(next)==-1||previous.getRelitivePosition(*this)-(*this).getRelitivePosition(next)==3){
		return 2;
	}
	else {
		return 3;
	}
}

int TrackNode::getDistance(TrackNode another){
	return abs(this->cellColumn-another.cellColumn)+abs(this->cellRow-another.cellRow);
}

double Track::getEvaluatedTime(double idealTime, double cornerRate, double UTurnRate){
	double time=0;
	for (int i=1; i<this->trackData.size()-1; i++){
		switch(this->trackData[i].getTurnState(this->trackData[i-1], this->trackData[i+1])){
		case 1:
			time+=idealTime;
			break;
		case 2:
		case 3:
			time+=idealTime*cornerRate;
			break;
		case 4:
			time+=idealTime*UTurnRate;
			break;
		default:
			break;
		}
	}
	return time;
}

Track::Track(int height, int width){
	this->height=height;
	this->width=width;
}

Track::Track(vector<TrackNode>trackData, Maze theMaze){
	this->height=theMaze.height;
	this->width=theMaze.width;
	this->startColumn=theMaze.startColumn;
	this->startRow=theMaze.startRow;
	this->endColumn=theMaze.endColumn;
	this->endRow=theMaze.endRow;
	this->trackData=trackData;
}

bool Track::isLegal(){
	for (int i=1; i<this->trackData.size()-1; i++){
		if (this->trackData[i].getDistance(this->trackData[i+1])!=1){
			return false;
		}
	}
	return true;
}

double Maze::getTotalHeight(double cornerRate){
	calculateHeight(cornerRate);
	int totalHeight=0;
	for (int i=0; i<height; i++){
		for (int j=0; j<width; j++){
			totalHeight+=mazeData[i][j].height;
		}
	}
	cout<<"Height:"<<totalHeight<<endl;//***测试用
	return totalHeight;
}

double Track::getTotalTime(){
	return trackData[trackData.size()-1].time;
}

};